#ifndef STX_ALGORITHM_IS_HEAP_UNTIL_HPP
#define STX_ALGORITHM_IS_HEAP_UNTIL_HPP

#include <stx/algorithm/common.hpp>

namespace stx {

template <class RandomAccessIterator, class Compare>
inline RandomAccessIterator
is_heap_until(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
    difference_type len = last - first;
    difference_type p = 0;
    difference_type c = 1;
    RandomAccessIterator pp = first;
    while (c < len) {
        RandomAccessIterator cp = first + c;
        if (comp(*pp, *cp)) {
            return cp;
        }
        ++c;
        ++cp;
        if (c == len) {
            return last;
        }
        if (comp(*pp, *cp)) {
            return cp;
        }
        ++p;
        ++pp;
        c = 2*p + 1;
    }
    return last;
}

template<class RandomAccessIterator>
inline RandomAccessIterator
is_heap_until(RandomAccessIterator first, RandomAccessIterator last)
{
    return stx::is_heap_until(
        first,
        last,
        stx::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}

} // namespace stx

#endif // STX_ALGORITHM_IS_HEAP_UNTIL_HPP
